package alogrithm;

import java.util.ArrayList;

import engine.Edge;
import engine.Vertex;
import gui.View;

public class Kruskal
{
   private ArrayList<Edge> edges;
   private Vertex gv[][];
   private int numEdges;

   private int size;
   private ArrayList<Vertex> vertices;

   public Kruskal(View view)
   {
      edges = view.getEdges();
      vertices = view.getVertices();
      numEdges = view.getEdges().size();
      size = vertices.size();
      gv = new Vertex[size][size];

      sortWeight();
      algorithm();

   }

   public void addGroup(Edge e)
   {
      addGroup(e.getFirstNode(), e.getSecondNode());
   }

   public void addGroup(Vertex v1, Vertex v2)
   {
      int i = 0, j = 0;

      while (gv[i][j] != null && i != size)
      {
         while (gv[i][j] != null && j != size)
            j++;
         j = 0;
         i++;
      }

      if (gv[0][0] == null)
      {
         gv[0][0] = v1;
         gv[0][1] = v2;
      }

   }

   public void addToGroup(int g, Vertex v)
   {
      for (int i = 0; i < size; i++)
         if (gv[g][i] == null)
         {
            gv[g][i] = v;
            break;
         }
   }

   public void algorithm()
   {
      int i = 0;
      int g1, g2;
      for (i = 0; i < edges.size(); i++)
         //in the initial iterate create the lowest edge as it own tree
         if (i == 0)
         {
            //create the tree
            newGroup(edges.get(0));
            //set the current edge status as visited, status=2
            edges.get(i).setStatus(2);
            //set both nodes connected by the current edges as visited
            edges.get(i).getFirstNode().setStatus(2);
            edges.get(i).getSecondNode().setStatus(2);
         }
         else
         {
            //get the first and second node
            Vertex v1 = edges.get(i).getFirstNode();
            Vertex v2 = edges.get(i).getSecondNode();

            //set both node as visited
            v1.setStatus(2);
            v2.setStatus(2);

            //check if the first node exist in another tree
            g1 = getGroup(v1);
            // check if the second node exist in another tree
            g2 = getGroup(v2);

            // both node not exist in any of created tree
            if (g1 == -1 && g2 == -1)
            {
               edges.get(i).setStatus(2);
               //create new tree
               newGroup(v1, v2);
            }
            // first node exist in another tree and second node does not
            else if (g1 != -1 && g2 == -1)
            {
               edges.get(i).setStatus(2);
               //add second node to the tree of first node
               addToGroup(g1, v2);
            }
            // second node exist in another tree and first node does not
            else if (g1 == -1 && g2 != -1)
            {
               edges.get(i).setStatus(2);
               //add first node to first node tree
               addToGroup(g2, v1);
            }
            else if (g1 == g2)
            {
            }
            //if both nodes exist in different trees
            else if (g1 != -1 && g2 != -1)
            {
               edges.get(i).setStatus(2);
               //all merge the tree to the oldest tree
               if (g1 < g2)
                  mergeGroup(g1, g2);
               else
                  mergeGroup(g2, g1);
            }
         }

   }

   // check
   public int getGroup(Vertex v)
   {
      int i = 0, j = 0;

      while (gv[i][j] != null && i != size)
      {
         while (gv[i][j] != null && j != size)
         {
            if (gv[i][j].equals(v))
               return i;
            j++;
         }

         j = 0;
         i++;
      }
      return -1;
   }

   public Vertex getNextUnvisit(Vertex v)
   {
      for (int i = 0; i < edges.size(); i++)
         if (edges.get(i).getFirstNode().equals(v))
         {
            if (edges.get(i).getSecondNode().getStatus() != 2)
               return edges.get(i).getSecondNode();
         }
         else if (edges.get(i).getSecondNode().equals(v))
            if (edges.get(i).getFirstNode().getStatus() != 2)
               return edges.get(i).getFirstNode();
      return null;
   }

   /*
    * public void secConnect(Vertex v) {
    * System.out.println("Node name "+v.getName()); markConnectEdge(v);
    * v.setStatus(2);
    * 
    * for(int i=0; i<edges.size(); i++) { if(edges.get(i).getStatus()==1) {
    * 
    * Vertex v1 = edges.get(i).getOther(v);
    * 
    * if(v1!=null && v1.getStatus()!=2) {
    * System.out.println("Edges "+edges.get(i).getWeight());
    * edges.get(i).setStatus(2); secConnect(v1); } } } }
    */
   public void markConnectEdge(Vertex vertex)
   {
      for (int i = 0; i < numEdges; i++)
         // check is the edges status is non active
         if (edges.get(i).getStatus() == 0
         && (edges.get(i).getFirstNode() == vertex || edges.get(i)
         .getSecondNode() == vertex))
            edges.get(i).setStatus(1);
   }

   public void mergeGroup(int g1, int g2)
   {
      for (int i = 0; i < size; i++)
         if (gv[g1][i] == null)
         {
            int j = 0;
            while (j != size && gv[g2][j] != null)
            {
               gv[g1][i] = gv[g2][j];
               // gv[g2][j]=null;
               i++;
               j++;
            }
            break;
         }
   }

   public void newGroup(Edge e)
   {
      newGroup(e.getFirstNode(), e.getSecondNode());
   }

   /*
    * public void print(Vertex v1) { int i=0; while(i<edges.size()) { Edge e =
    * edges.get(i);
    * 
    * if(e.getFirstNode()==v1) { v1.setStatus(2);
    * System.out.println(v1.getName()); if(e.getSecondNode().getStatus()!=2)
    * print(e.getSecondNode()); else { Vertex v =
    * getNextUnvisit(e.getSecondNode()); if(v!=null) {
    * System.out.print(" Next "+v.getName()); print(v); } }
    * 
    * } else if(e.getSecondNode()==v1) { v1.setStatus(2);
    * System.out.println(v1.getName());
    * 
    * if(e.getFirstNode().getStatus()!=2) print(e.getFirstNode()); else { Vertex
    * v = getNextUnvisit(e.getFirstNode()); if(v!=null) {
    * System.out.print(" Next "+v.getName()); print(v); } }
    * 
    * }
    * 
    * i++; } }
    */

   public void newGroup(Vertex v1, Vertex v2)
   {
      for (int i = 0; i < size; i++)
         if (gv[i][0] == null)
         {
            gv[i][0] = v1;
            gv[i][1] = v2;
            break;
         }
   }

   public void sortWeight()
   {
      Edge tmp;
      for (int i = 0; i < numEdges; i++)
         for (int j = 0; j < numEdges; j++)
            if (edges.get(i).getWeight() < edges.get(j).getWeight())
            {
               tmp = edges.get(i);
               edges.set(i, edges.get(j));
               edges.set(j, tmp);
            }
   }

}
